package binarytree


type TreeNode struct{
	Val int
	Left,Right *TreeNode
}
func sumOfLeftLeaves(root *TreeNode) int {
	var res int
	getSumPreOrder(root,&res)
	return res
}

// 先序递归
func getSumPreOrder(root *TreeNode, sum *int) {
	// 确定边界
	if root == nil {
		return 
	}

	// 先序
	if root.Left!=nil && root.Left.Left==nil && root.Left.Right==nil {
		// 左叶子 计算
		*sum = *sum + root.Left.Val
	}
	// 左
	getSumPreOrder(root.Left, sum)
	getSumPreOrder(root.Right, sum)
}

// 后序遍历
func getSumPostOrder(root *TreeNode) int{
	if root == nil {
		return 0
	}
	// 遇到左叶子节点 记录数字然后递归
	leftVal := getSumPostOrder(root.Left)  // 左
	rightVal := getSumPostOrder(root.Right)  // 右

	midVal :=0
	if root.Left!=nil && (root.Left.Left==nil && root.Left.Right==nil) {
		// 左叶子 计算
		midVal = root.Left.Val
	}
	sum := midVal + leftVal + rightVal
	return sum
}


// class Solution {
// 	public:
// 		// 前序迭代版本
// 		int sumOfLeftLeaves(TreeNode* root) {
// 			stack<TreeNode*> st;
// 			if (root == NULL) return 0;
// 			st.push(root);
// 			int result = 0;
// 			while (!st.empty()) {
// 				TreeNode* node = st.top();
// 				st.pop();
// 				if (node->left != NULL && node->left->left == NULL && node->left->right == NULL) {
// 					result += node->left->val;
// 				}
// 				if (node->right) st.push(node->right);
// 				if (node->left) st.push(node->left);
// 			}
// 			return result;
// 		}
// 	};